package hyy_2022;


import commons.TreeNode;

/**
 * 二叉搜索树,第K大节点的值
 *
 * 所谓的第K大就是二叉搜索树中序遍历后的倒序第K个元素,不看示例还真不知道这个题的意思
 *
 * 中序遍历是递增-顺序是左节点,根节点,右节点
 * 中序遍历后的倒序是递减-顺序是右节点,根节点,左节点
 *
 */
public class _0805_Offer54_KthLargest {
    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(3);
        TreeNode node2 = new TreeNode(1);
        TreeNode node3 = new TreeNode(4);
        TreeNode node4 = new TreeNode(2);
        node1.left = node2;
        node1.right = node3;
        node2.left = null;
        node2.right = node4;
        System.out.println("--" + new _0805_Offer54_KthLargest().kthLargest(node1,3));

    }

    int k;
    int res;
    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return res;
    }


    public void dfs(TreeNode root) {
        if(root == null) {
            return;
        }
        dfs(root.right);
        if(k == 0) {
            return;
        }
        System.out.println(root.val);
        if(--k == 0) {
            res = root.val;
            return;
        }
        dfs(root.left);

    }

}
